1. Field of the Invention
The invention generally relates to a pattern recognition system, and in particular to detecting an image of an object which has the shape of a conic section, including a circle, an ellipse, a parabola and a hyperbola.
2. Description of Prior Art
One of the major problems in automatic assembly is detecting and identifying the parts to be assembled when the parts lie in a bin or on a conveyer belt in an unknown position and/or orientation. In current methods, one takes a video image of the object, then finds edges in this image, i.e. sharp changes in the light intensity, which are generated by the outlines or other features of the object. The resulting "edge map" is then processed to identify the object. If the position and orientation of the object are known in advance then one can compare the edge map with a data-base of edge maps obtained from known objects and determine if there is a match. However, for an objects in arbitrary position and orientation (the usual case) one would have to shift and rotate the image in every possible way and try to find a match for each possible position and orientation, which is prohibitively expensive.
Most methods used to deal with this difficulty are based on the Hough method (the patent cited), most commonly applied to finding straight lines. The Hough method for straight lines is as follows. A line can be described by two parameters, e.g. the slope and intercept. One constructs a parameter space, in this case a plane with the slope and intercept as its coordinates. At each edge point in the edge map it is possible to draw a bundle of lines, all having different slopes, and all passing through that edge point. This bundle is represented in the parameter space by a straight line whose points are the parameters of the lines belonging to the bundle. For each point on the edge map one draws the corresponding line in the parameter space. If the edges lie on one straight line in the edge map (i.e. there is a visible line in the image), then the corresponding lines in the parameter space will meet at one point. This is because the line on which the visible edges lie is common to all the line bundles passing through the edges. The parameters of this line are the coordinates of the common point in the parameter space. Thus, by searching for common points in the parameters space, one can find lines in the image without a prior knowledge of their position or orientation. The method is already implemented on a VLSI chip.
The method can be extended to more complicated shapes. The higher number of parameters involved leads to a parameter space of high dimensionality which becomes impractical to store and conduct searches in. However, most industrial parts contain, besides straight lines, segments which are circular or elliptic or seen as such. E.g. a side view of a circle is seen as an ellipse, thus detection of ellipses is essential. It is also sufficient in many applications because a side view of an ellipse is just another ellipse, making an ellipse detection method useful for a wide variety of applications.
To use the Hough method for ellipse detection would require searching for common points in a five dimensional parameter space, which is the minimum needed to described an ellipse (and other conic sections) and this is impractical for current machines. Therefore it is highly desirable to reduce the dimensionality of the problem to two and thus make the detection of conic sections as practical as the detection of straight lines.
Tsukune et al describe a method of reducing the dimensionality of the parameter space needed. They find edges in the images and the directions of these edges. For each pair of edges having the same direction, they find the midpoint between the edges. They histogram all the midpoints in a two dimensional array to find the most probable location of a center of an ellipse. In the next step a second two dimensional histogram (the H-B histogram) is needed to find two more parameters of the ellipse. A final histogram, involving all pairs of edges possibly belonging to an ellipse, is used to find the last ellipse parameter. Similar methods are used in the other references cited.
There are several problems with these methods. Finding the location of edges in the image is quite difficult because of noise and other distorsions in the image. Finding directions of the edges, i.e. the direction of a small line segment separating the light and dark patches in the image around a certain location, is much harder and the results are very unreliable as is well known to persons skilled in the art. This is because a direction involves finding the location of at least two nearby points on this edge line segment, and a small error in one of them leads to a large error in the direction. Therefore, the centers found based on this information are unreliable and need a high amount of processing to reject the incorrect ones.
Another problem is the several stages of complicated histogramming needed in these methods which are time and memory consuming.